1912D - Divisibility Test - CodeForces Solution

#include "bits/stdc++.h"
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define endl  "\n"
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define sz(x) (int)((x).size())
#define debug(x) cout << #x << "  " << x << "\n"
#define vi vector<int>
#define mem(c, a) memset(c, a, sizeof(c))
#define setbit(x) __builtin_popcountll(x)
const double eps = 1e-6;
const int N = 2e5 + 5;
const int inf = 1e18;
//const int mod = 1e9 + 7;
const int mod = 998244353;




void solve(int t_case)
{
  int b , n; cin>>b>>n; 

  int t = 0 , k = 0; 

  set<int>s; int c = 1; int d = 1; int ok = 0;     

  for(int i = 1; i < 2*n; i++)
  {  
     c *= b; 
     c %= n;  
     if(c == 0) 
     {
      ok = 1;
      break;
     }
     if(c == 1)
     {
       ok = 2;
       break; 
     }
     d++;
  }
  if(ok > 0)
  {
     if(ok == 1)
     {
        t = 1 , k = d; 
     }
     else
     {
        t = 2 , k = d; c = 1;  
 
        for(int i = 0 ; i < d; i++)
        { 
           if(k == 1) break; 

           if(c == n-1)
           {
             //debug(i); 
             if((d % i == 0) && ((d/i) % 2 == 0)) 
             {
               t = 3 , k = i; break;
             }
           }
           c *= b; c %= n; 
        }
     }
  }
  if(t == 0)
  {
    cout<<"0\n"; 
  }
  else cout<<t<<' '<<k<<endl; 
}





void precomp(){}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

// cout << setprecision(12) << fixed;

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	//sieve();
//    precomp(); 
  

	int tests = 1;
	cin>>tests;

	for(int i = 1; i <= tests ; i++) solve(i);
	return 0;
}